package com.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class FiveDataTest {

    private static List<Integer> list = new ArrayList<>();
    private static List<Integer> selectedElementsList = new ArrayList<>();
    private static int targetNumber;
    private static int closestSum = Integer.MIN_VALUE;
    private static Random random = new Random();

    public static List<Integer> findClosestSum(List<Integer> data, int target) {
        list = data;
        targetNumber = target;

        findClosestSumHelper(0, 0);

        return selectedElementsList;
    }

    private static void findClosestSumHelper(int index, int currentSum) {
        if (index == 5) {
            if (currentSum < targetNumber && currentSum > closestSum) {
                closestSum = currentSum;
                selectedElementsList = new ArrayList<>(list.subList(0, 5));
            }
            return;
        }

        for (int i = index; i < list.size(); i++) {
            swap(index, i);
            findClosestSumHelper(index + 1, currentSum + list.get(index));
            swap(index, i);
        }
    }

    private static void swap(int i, int j) {
        int temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

}
